package bfs;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/2/16
 * @verdion 1.0.0
 */
public class OpenLock {

    public int openLock(String[] deadends, String target) {
        if(target == null || target.length() != 4){
            return -1;
        }
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        queue.add("0000");
        visited.add("0000");
        int depth = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int a = 0; a < size; a++) {
                String cur = queue.poll();
                if (deads.contains(cur)) {
                    continue;
                }
                if (cur.equals(target)) {
                    return depth;
                }
                for (int i = 0; i < 4; i++) {
                    for (int j = -1; j <= 1; j += 2) {
                        int tmp = cur.charAt(i) - '0';
                        tmp = (tmp + j + 10) % 10;
                        String next = cur.substring(0, i) + tmp + cur.substring(i + 1, 4);
                        if (!visited.contains(next)) {
                            visited.add(next);
                            queue.add(next);
                        }
                    }
                }
            }
            depth++;
        }
        return -1;
    }
}
